/*
https://leetcode.cn/problems/numbers-with-repeated-digits/submissions/573827446/
至少有一位重复数字
数位dp
*/

class Solution {
public:
    int A[10][10];
    Solution(){
//计算排列数
        for(int i=0;i<=9;i++){
            A[0][i]=1;
            for(int j=1;j<i;j++){
                A[j][i]=A[j-1][i]*(i-j+1);
            }
        }
    }
    int numDupDigitsAtMostN(int n) {
        bool used[10]={};
        vector<short> digit;
        int k=n,m=0;
        while(k>0){//将数字n的每一位分解出来
            digit.emplace_back(k%10);
            k/=10;
        }
//计算[1,099999(<n的全9最大值)]互不相同的数字个数
        for(int i=digit.size()-2;i>-1;i--){
            k+=9*A[i][9];
        }
//计算[100000,a00000)互不相同的数字个数并累加入k
        k+=(digit.back()-1)*A[digit.size()-1][9];
        used[digit.back()]=1;m++;
//每次循环分别计算[a00000,ab0000)互不相同的数字个数并累加入k
        for(int i=digit.size()-2;i>-1;i--){
            for(int j=0;j<digit[i];j++){//当前位只能取前面没出现过的数，所以只计算j没使用时的组合数
                if(used[j]==0)k+=A[i][9-m];//相当于固定前面的l个数，后面的不相同的数为(10-l)(10-l-1)...
            }
            if(used[digit[i]]){return n-k;}//若当前数位在前面用过，后面的都属于有重复数字
            used[digit[i]]=1;m++;//记录用过的数
        }
        return n-k-1;
    }
};